//图的深度优先搜寻（dfs）
/*
  类似树的先根遍历
*/

#include "MGraph.h"
#include <iostream>

using namespace std;

bool visited[MaxVertexNum]; //访问数组，用于标记对应顶点是否被访问过

inline void visit(int v) //访问操作
{
    cout << v << ' ';
    return;
}

//从顶点v开始的深搜
void DFS(MGraph G, int v)
{
    visit(v);          //访问操作
    visited[v] = true; //标记已访问

    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        if (!visited[w]) //若w为未访问邻接顶点，则递归
            DFS(G, w);
}

int main()
{
    MGraph G;        //以邻接矩阵来实现，可确保dfs遍历序列唯一
    G.DirStatue = 0; //该图为无向图，且不带权
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该带权图的邻接矩阵
    cout << "please input (x y):\n";
    for (int x, y, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y;
        AddEdge(G, x, y);
    }

    //测试代码，以顶点1开始遍历
    DFS(G, 1);
    return 0;
}